package lesson9;

import java.util.Arrays;

public class buildHeap {
	
		public static void main(String[] args) {
			
			int[] array = {9,5,4,80,6,7,0,10};
			System.out.println(Arrays.toString(array));
			array = heapSort(array);
			System.out.println(Arrays.toString(array));
		}

		private static int[] buildHeap(int[] array) {
			
			for(int i = 0; i < array.length; i++)
			{
				int nodeIndex = i;
				while(nodeIndex != 0)
				{
					int parentIndex = (nodeIndex-1)/2;
					if(array[nodeIndex] > array[parentIndex])
					{
						int temp = array[nodeIndex];
						array[nodeIndex] = array[parentIndex];
						array[parentIndex] = temp;
					}
					nodeIndex = parentIndex;
				}
				
			}
			
			
			return array;
		}


		public static int[] heapSort(int[] array)
		{
			//we build max heap out of the array
			array = buildHeap(array);
			//for n iterations we do:
			for(int i = 0; i < array.length; i++)
			{
				int heapSize = array.length-i-1;
			  // 1: swap first element with last element of the heap, heap size --
				swap(array, 0, heapSize);
			  // 2: rearrange heap so that new root comes into place:
				int nodeIndex = 0;
				while(true)
				{
					int leftChildIndex = 2*nodeIndex+1;
					int rightChildIndex = 2*nodeIndex+2;
				//2.1: check if node has children. If not - break
					if(leftChildIndex >= heapSize)
					{
						//node is a leaf ; break
						break;
					}
					else//has left child. Check if has right as well
					if(rightChildIndex >= heapSize)
					{
						//node has only 1 child and that is the left one. Check and swap with the left.
						if(array[leftChildIndex] > array[nodeIndex])
						{
							swap(array,leftChildIndex, nodeIndex);
							nodeIndex = leftChildIndex;
							continue;
						}
						else//no need to swap, heap is heapified
						{
							break;
						}
					}
					else//has two children
					{
						//check with bigger child
						int biggerChildIndex = -1;
						if(array[leftChildIndex] > array[rightChildIndex])
							biggerChildIndex = leftChildIndex;
						else
							biggerChildIndex = rightChildIndex;
						//check and swap with bigger child
						if(array[biggerChildIndex] > array[nodeIndex])
						{
							swap(array,biggerChildIndex, nodeIndex);
							nodeIndex = biggerChildIndex;
							continue;
						}
						else//no need to swap, heap is heapified
						{
							break;
						}
					}
				}
				System.out.println(Arrays.toString(array));
			}
			return array;
		}

		private static void swap(int[] a, int i, int j) 
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
}

